Text Tagging Algorithm

This is the algorithm we’re planning to use at the moment to tag text with the meanings of the words in it.

Datasets

There are quite a few really big datasets used in this algorithm, so that we have a better chance of correlating words better with more information. Here are all of the ones we’ve decided on currently. [1]

  • Wikidata

    Wikidata is a very large database of structured information about pretty much everything. [2] It’s a free knowledge base that’s regularly being edited by humans and machines to reflect the real world. We can use live data from the Wikidata API, or the easier-to-use Wikidata SPARQL endpoint. We can also use the Wikidata data dumps. Currently we still have to decide which way we’re going with. Some salient points to keep in mind:

    • Live data:
      • Because humans edit Wikidata very, very frequently, it’s a pretty strong possibility for abuse by entering false information. This kind of stuff, like on Wikipedia, is usually removed very quickly by another person who happens to be checking on the page at the moment, but there’s still enough latency that if we query at the wrong moment, we could get very false information and mess up the results.
      • Having said that, it’s very unlikely for someone to do this to the kind of things we’re targeting in education, because there’s no real reason to. People mostly do this for stuff like very politicized or controversial objects, which ours are extremely unlikely to be.
      • Having said that, there are always trolls.
      • A possible solution could be to query 5 or so times, and make sure the results are relatively consistent. This approach feels hackish, though, and will probably break down at the worst possible moment.
      • The SPARQL endpoint is really great and will allow us to have a really good layer of abstraction which we otherwise would have to build ourselves over the JSON data dumps.
    • Data dumps:
      • The obvious issue with data dumps is that they’re not updated very regularly. Maybe we don’t need immediate, 100% up-to-date data, especially because things to do with education are not very likely to change.
      • However, we still need to make sure the info’s not going too stale - but maybe it’s not often enough that a human can’t do it.
      • Still, we may determine that’s it’s useful enough to have live data that we get the server to download it every now and then, maybe every 2 months or so. Doing so, though, would cost us a lot of bandwidth and feels unnecessary.
      • Another, less major, issue with data dumps is the amount of space that’s needed to store them. At time of writing, Wikidata has a little less than 25 million data items, which could cost a lot of space.
  • Google Ngram [3]

    Ngrams would be very useful not only in creating stronger associations with words that appear together often, but also to create stronger associates with words that appear together often in a particular time peroid, and this is where the Google Ngram data lends itself a lot of usefulness for our alogoritm. If one of the words used were very popular in a certain time period, and that time period has attributes associated with specific entities in, say, the Wikidata data for a particular word, we can establish a stronger confidence in that particular entity being the meaning of that word. There are some notable pitfalls, like OCR errors, bias towards scientific articles, and abudance of stopwords, but so far we don’t think these are bad enough to completely invalidate the use of this dataset. However, they are things to keep in mind. We can use this dataset directly by just downloading it, or we can use a streaming Python library, google-ngram-downloader. Here, the choice is mostly about storage.

  • CommonCrawl [MAYBE]

    The CommonCrawl dataset is a huge mash of crawling data collected over 7 years by the CommonCrawl nonprofit. It’s going to be used to train a word2vec model to have a better idea of the similarity between words. Of course, because we won’t know the context of the words, we’ll only use this data to create stronger associations. Ultimately, that’s what we’re using all the data for, to have as much confidence as possible that two words are connected with a specific meaning. The only option available for using the CommonCrawl data is their monthly data dumps.

    Note

    The reason for the Maybe here is because the CommonCrawl data is very complex, (and possibly unnecessary) and can be hard to parse into a format understandable by word2vec. There are a few guides available, and there’s also a version of the data that’s already been parsed here (see section under ‘Download pre-trained word vectors’), but it’s unsure how up-to-date this data is. It’s the simplest option if it’s updated enough, maybe 2015-ish. But the problem with that is we don’t know if it’ll be updated later, when we want to update it in, like, 2025 or something, and then we’ll have the parsing problem.

  • WordNet

    WordNet is an extremely common dataset in NLP, it’s a relationship graph connecting different definitions of words. We’ll be using it to compare definitions, similar to the Lesk word-sense disambugation algorithm, and to establish parent-child relationships.

Warning

The data from this point onwords starts getting a little less reliable and a little more experimental. However, we feel they are useful enough to merit use here. There will also be numerous references to confusing & long scientific articles that you don’t need to read.

  • VerbNet [4]

    VerbNet is very similar to WordNet, as suggested by the name, and it does almost the same thing WordNet does but with verbs, but it also provides some very useful additional data as well. It provides usage information for the verbs, what it calls frames. For example, VerbNet has a class called weather, that contains verbs like blow, clear, drizzle, fog, freeze, among 22 others. The three frames it provides for the class are represented like this (where V is the verb, and ‘E’ is Event):

    • Example: “It’s raining cats and dogs.”
      Roles: Theme [+Concrete | +Force]
      POS: It V NP.Theme
      Syntax: (It) ([+Be]) V Theme
      Semantics: WEATHER(DURING(E), WEATHER_TYPE, THEME)
    • Example: “It was pelting with rain.”
      Roles: Theme [+Concrete | +Force]
      POS: It V PP.Theme
      Syntax: (It[+Be]) V {With} Theme
      Semantics: WEATHER(DURING(E), WEATHER_TYPE, THEME)

    After only some examination, you can see how useful this data can be in reinforcing the nouns associated with certain verbs in a sentence. The semantic meaning will also be extremely useful to know the true meaning of a sentence, especially when it involves negatives.

    One of the possible problems is the mapping of the attributes of the roles ([+Concrete | +Force]) to Wikidata properties. Some of these attributes are maddeningly nonspecific.

  • PropBank

    The PropBank is described by its creators as “an annotated corpus of semantic roles”. It’s very similar to VerbNet, it just provides some of the more esoteric verbs like condense and others.

  • FrameNet

    FrameNet is also very similar to both of the above, it provides more words, and not just verbs.

  • OntoNote Sense Groupings

    Very similar, more words.

Note

Because the above four datasets are so similar, but ever so slightly different, one of the problems we might face is figuring out a way to commonly represent all the data in them. However, the algorithm steps below assumes that we did figure it out. Another one as mentioned in the VerbNet section is the mapping of semantic roles to Wikidata properties.

Libraries

Here is a listing of all of the libraries we’ll be using.

  • SpaCy

    We’ll be using SpaCy mainly for dependency parsing and POS tagging. Right now, 1.0 has just been released, meaning it’s undergoing some changes, but those are mainly in more advnaced features. One of the useful changes underway right now is the addition of a compressed version of the CommonCrawl data, which may solve the main problem right now with the CommonCrawl.

    SpaCy is written in Cython, and it’s super fast and has been industry strength for about 2 years now. Pretty reliable.

  • NLTK

    Über mature, fast NLP library in Python. Mainly we’ll be using it to obtain the VerbNet, PropBank, and FrameNet data.

  • Gensim

    Gensim is another super mature NLP library, mainly used for topic modelling. It’ll be used for the word2vec and LDA algorithms that it provides.

  • [DEPENDS ON: Whether we are using live Wikidata data] SPARQL Python

    If we’re using the live data, the best method to do so is to use the SPARQL endpoint, which is a way to query Wikidata in a language very similar to SQL called SPARQL. It’s unsure how mature this libary is, however, a developer in W3C, the creator of the SPARQL standard, was involved in the creation of this project, so it’s very likely to be correct.

Glossary

To make the rest of this explanation clear, we have to define some specific terms.

vocabulary
All the meanings we know. In our case, that’s Wikidata.
term
A single word or a sequence of words. For example, song, word, miley cyrus.
tagged term
A term tagged with its specific meaning in context. In our case, this will most likely be a Wikidata entity for nouns, phrases, and such, and a
text segmentation
segmentation
A segmentation is a sequence of terms where each non-stopword word is covered by a term, and no two terms overlap. For example, “Why is it possible to magnetize an iron bar but not a copper bar?” and “Why is it possible to magnetize an iron bar but not a copper bar?” are both valid segmentations of “Why is it possible to magnetize an iron bar but not a copper bar?” (though only one of them represents the semantic meaning). A segmentation can also contain tagged terms instead of terms.
concept vector
Basically a list of all the possible meanings a term can have.

The Algorithm

The actual algorithm is heavily based on a research paper made by the Microsoft Research team, called Short Text Understanding Through Semantic Analysis. It’ll give you the gist of this algorithm, and a little bit more specific details as well.

  1. We recieve the main question itself, along with the description given.

  2. We mark any stopwords, though we don’t remove them just yet, because they might be part of a larger term.

  3. We use the spaCy dependency parser and PoS tagger to construct a dependency tree of the main question with each word/phrase’s PoS tag.

  4. We start working with the main question. The first thing we need to do is determine every possible segmentation of the question.

    1. We look in our vocabulary for all the tagged terms that contain each word (specifically, the nouns). We also consider two or more words that are marked as compound by the dependency parser to be one term. For example, in “Why is it possible to magnetize an iron bar but not a copper bar?”, “iron bar” and “copper bar” are terms because they’re marked as compounds, and “iron” and “copper” and “bar” are terms because they appear in the our vocabulary.
    2. We place each tagged term in an as-yet unconnected graph structure.

  5. To start connecting the graph, we need to determine each tagged term‘s Affinity Score with each other. This is where all that data comes in. The Affinity Score is calculated using a variety of factors:

    • Looking at each verb in the sentence that’s syntatically related to each noun, we look at PropBank, VerbNet, and FrameNet and make sure that the usage of the verb to that specific meaning of the noun has the proper attributes to fill the role.

      That was a bit confusing; as an example, let’s take “How do birds know where to go when they migrate?”. The dependency parser says that the verb “migrate” is related to the noun “they”, by “nsubj” (noun subject). Using NLTK’s pronoun resolution [5], we figure out that “they” refers to “birds”. We take the lemma of that, which is “bird”. (In case bird had an adjective referring to it, like “nice”, we would ignore it.) Looking in PropBank, the verb “migrate” has a role “entity in motion”, which we can match to the meaning of “bird” that’s an animal, because it’s an Entity in Wikidata and it’s also an Animal, which we know has an attribute of motion. We can also look in Groupings and see that the there needs to be a noun before “migrate” which is an agent, and has the property of being animate, which a bird does.

    • Looking at each meaning of each term in relation to each other, for example, whether they have the same subclass, how far up does that subclass go, wheter one is an attribute of the other, whether one is in the name of an attribute of the other (for example of “country” and “population”), etc.

      Note

      We have yet to decide an exact list of all the relations that we’ll be taking into account from Wikidata data. However, we think the overall path is clear.

    • Looking in FrameNet to check the usage of adjectives, in a similar manner to that of verbs. Using the adjective “nice” as an example, FrameNet reports that there can be a variety of core roles in the sentence, for example the “Affected_party”, anything, the “Judge”, who needs to be animate, a “Degree”, etc.

      Note

      This might be a little bit complex and we might have to simplify the FrameNet dataset.

    • Looking at words appearing in specific definitions of words, from WordNet. Each word in PropBank, FrameNet, VerbNet, and Groupings cotains an appropriate matching up to a particular synset in WordNet.

    • Looking at the word2vec similarity between specific words. On its own, semantic meanings could be messed up, but combining it with all these other relations should make it a useful addition.

    • Looking at Google Ngram data, how often two words appear next to each other right now, whether they have any attributes that are connected based on the year, etc.

Each of these things would affect the weight attached to connections between two tagged terms in some way, making them stronger or weaker. We could also take into consideration the relations between the words in the question and keywords in the description, these keywords being obtained by using a LDA on the description to extract common related words.
  1. In the end, we take the tagged terms that have the strongest connections to each other as the final segmentation.

Warning

One major problem with the above algorithm is how many different meanings we would have to compare. For example, the word “bird” has about 20,899 meanings in Wikidata currently, referring to such utterly untrelated things as rock bands, albums, and last names. As a result, this algorithm might be painfully ineffecient. A possible solution to this problem comes in the form of a half-formed idea of mine, modelling how to human brain does it.

We could use the relevant contexual information provided by the subject and the tags to assemble a sort of “current mental state” of the computer. The algorithm could ignore anything that does not match some represention of its mental state, but it’s as-yet unsure as to how that might be determined.

Footnotes

[1]This might be a little overkill, but we’re basically just throwing data at the algorithm anyway, might as well.
[2]Two good graphical ways to explore Wikidata data are the Reasonator and the Wikidata Graph Builder.
[3]An excellent visulaizer for Ngram data is the Google Ngram Viewer
[4]Some (extremely long) articles on VerbNet, the dissertation and the easier-to-read counterpart, the guidelines.
[5]Though it’s extremely poorly documented, NLTK does have an anaphora resolution function, that can be found here.